\usepackage{listings}
\lstset{language=Java,
        basicstyle=\small}

\usepackage{graphicx}
\usepackage{hyperref}

\hypersetup{
  colorlinks=true,
  urlcolor=blue,
  linkcolor=black
}
\mode<article>{\usepackage{fullpage}}

\title{Lecture Nine -- Trees}
\author{Matt Bone}
\date{\today}

\begin{document}

\mode<article>{\maketitle}
\tableofcontents
\mode<article>{\pagebreak}
\mode<presentation>{\frame{\titlepage}}
\mode<article>{\setlength{\parskip}{.25cm}}
\mode<all>{\bibliographystyle{abbrvnat}}

\section{Trees}
Everything we've seen so far has been a linear data structure.  Now we
get into more complicated data structures.

\subsection{A Tree Example}\label{sec:example}
Consider this simple xml snippet:

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{An XML Example}}
  \begin{verbatim}
  <bankaccount>
    <name>Checking</name>
    <balance>
      <dollars>100</dollars>
      <cents>23</cents>
    </balance>
  </bankaccount>
  \end{verbatim}
\end{frame}

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{An XML Example...As a Tree}}
  One of of conceptualizing this, is to think of it as a tree:
  \begin{center}\includegraphics[width=4cm]{xml}\end{center}
\end{frame}

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{An Simple Tree Example}}
  Another example of a tree that we will examine is shown below:
  \begin{center}\includegraphics[width=6cm]{sample_tree}\end{center}
\end{frame}

\subsection{Tree Terminology}

\begin{description}

\item[Branch] line from a root element (also called a node) to
 a subtree.  Branches are also sometimes called edges.

\item[Leaf] An element with no subtrees (no children).

\item[Parent] If element $x$ has a subtree whose root is element $y$
then $x$ is the parent of $y$.

\item[Child] If element $x$ has a subtree whose root is element $y$,
then $y$ is the child of $x$.

\item[Ancestor] If element $y$ has parent element $x$ then $x$ and all
of its parents, and the parent's parents, etc, etc, are ancestors.  A
parent is always an ancestor, but an ancestor is not necessarily a
parent.

\item[Path] A route from an ancestor to a descendant node.

\item[Height] ``The number of branches between the root and the
farthest leaf.''
  
\item[Level or Depth] If element $x$ is the root, it's level is
$0$. Otherwise, it's level is the number of branches in the path
between the root node and $x$. (Much easier to visualize, see picture
on page 369)

\end{description}

\subsection{Tree Traversal}
Oftentimes when we deal with trees in computer science, we will want
to visit every node once.  We can call this \emph{tree traversal}.  
Occasionally we may think of this as \emph{serialization}, but that can
be a somewhat loaded term.

As is usually the case, this is not done haphazardly; instead there
are two common cases of tree traversal: \emph{depth first search} or
DFS, and \emph{breadth first search} or BFS.

\subsubsection{Depth First Search}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Depth First Search}}
  In a DFS, we go down the tree first.  Although it is not a requirement,
  one technique is to traverse the ``leftmost'' path first and then move to the
  next path to the ``right.''

  If we consider the numerical tree
  in section \ref{sec:example}, the traversal of the tree might be: 
  42, 45, 46, 47, 53, 17, 20, 32
\end{frame}

\subsubsection{Breadth First Search}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Breadth First Search}}
  In a BFS, we go across the tree first.  That is, every element in a
  level is visited before any of their subtrees are visited.

  If we consider the numerical tree
  in section \ref{sec:example}, the traversal of the tree might be: 
  42, 45, 53, 46, 17, 20, 32, 47
\end{frame}
\section{Binary Trees}

\subsection{A Formal definition}
From the book, page 366:

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Binary Trees: Formal Definition}}
  A \emph{binary tree} $t$ is either empty or consists of an element, called
  the root element, and two distinct binary trees called the left
  subtree and right subtree of $t$.
\end{frame}


Here we see that the definition of a binary tree is recursive.  Many
techniques for dealing with trees are recursive, so it is imperative
that you have a firm grasp on recursion before we proceed.

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Binary Tree Example}}
  A simple modification of the tree in section \ref{sec:example} yields
  the following binary tree:
  \begin{center}\includegraphics[width=4cm]{sample_binary_tree}\end{center}
\end{frame}

\subsection{More Tree Terminology}
\begin{description}
\item[Two Tree]: A binary tree in which every node has either two
children or no children.

\item[Full] A tree in which all non-leaf elements have the maximum
number of allowed children and all leaves are on the same level. (See
page 370).

\item[Complete] A tree that is full until the second to last level;
all nodes in the final level are as far to the left as possible. A
full binary tree is necessarily complete, but a complete binary tree
is not necessarily full.  (See page 371)
\end{description}

\subsection{Properties}
These are some interesting and important properties of binary trees.
Though I have pulled these from an alternate source, they are 
similar to those from our book on page 373.
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Properties of Binary Trees}}
  \begin{itemize}
    \item There are at most $2^d$ elements at depth $d$ of a binary tree.
    \item A binary tree of height $h$ has at most $2^{h+1}- 1$ nodes.
    \item A binary tree with $n$ nodes has height at least $ceiling(lg(n+1) - 1)$. 
  \end{itemize}
  \cite{baase00} page 81
\end{frame}

Hopefully someday you will get a chance to prove these.  Today,
though, we will just look at what they mean and how to use them.

\subsection{Binary Search Trees}
Now that we have some theoretical underpinning, we can use binary
trees to get some real work done.  So now we take a look at a subclass
of binary trees called binary search trees.  Binary search trees have
all the properties of regular binary tress with the added stipulation
that each element in the left subtree is less than the root and each
element in the right subtree is greater than the root.

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Binary Search Trees}}
  \begin{center}\includegraphics[width=6cm]{sample_binary_search_tree}\end{center}
\end{frame}

\section{Applications}

\subsection{Binary Search Trees and Sets}
We've already talked briefly about sets.  Remember that a set is data
structure that contains no duplicate objects (think equality here, not
identity).  We've already talked about implementing a set using hashing 
already. Now we will see how to implement a set using a binary tree (
note, this implementation is somewhat naive as we shall see).

\subsubsection{TANSTAAFL}
There Ain't No Such Thing As A Free Lunch

Though we now see that we can search through a binary search tree and
find elements rather quickly, we should step back and realize that
these trees do not pop out of thin air.  We must build them up
somehow.

\subsubsection{Contains}
This is what we've already seen in our number example.  Since the
binary search tree assumes that we are able to compare the values of
objects, we simply try to find the object in the tree.  Assume we're
looking for $x$ in the tree.  To start out we compare $x$ to the
root.  If $x$ is less than the root we go left.  If it's equal we're
done.  If it's greater than the root we go right. We repeat this
process (it's recursive).  \emph{One important thing to notice is that
the worst case will always be the height of the tree.}  If this is
the case, what is a desirable property of binary search trees?
  
\subsubsection{Add }
Adding a new element to the tree is similar to searching for an
element.  As before, we look at the root, go left if our element is
less, go right if it is more.  When we encounter a leaf (and we will
encounter one and only one leaf), we insert our new element to the
left of the leaf it is smaller or to the right it if is larger.

Here we see that we don't get a free lunch.  We're building up this
tree as we go along by traversing it each time to find the appropriate
place to add items.  What is this doing and why are we doing it?
Well, by we're really building logic into the tree.  An item's place
in the tree tells us something about its value.  So now, by taking a
little more time during the insertion, we can search for the object
quite quickly.

\subsubsection{Remove}
Removal is a slightly more sophisticated operation.  First off, as
always, we find the node to remove in the tree.  If the node happens
to be a leaf, we can remove it with no problems.  Similarly, if the
node only has one child, we remove it, and the node's child becomes
it's parent's new child.  Things are trickier when we want to remove a
node with two children.  Say we want to remove node $n$ which has
both left and right subtrees.  The approach is to find the smallest
node in the right subtree, and put that node where node $n$
currently is.  Then we remove node $n$ from the tree.

\subsection{Evaluation Trees}

\mode<all>{\bibliography{sources}}

\end{document}
